package com.yuren.codecrushlearn.Q5200;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description:
 * Robin Karp算法
 * @author 10204
 * @date 2025-05-02 23:24
 */
public class Q5242 {
    // 定义一个质数作为模数(减少hash冲突的可能)，便于hash值的计算和重新赋值
    private static final int PRIME = 101;

    public List<Integer> rk(String mstr, String sstr) {
        List<Integer> result = new ArrayList<>();
        int n = mstr.length();
        int m = sstr.length();

        if (m > n) {
            return result;
        }

        // 计算子串 sstr 的哈希值和主串 mstr 第一个窗口的哈希值，窗口大小为子串的长度
        long sstrHash = calculateHash(sstr, m);
        long mstrHash = calculateHash(mstr, m);

        for (int i = 0; i <= n - m; i++) {
            // 检查当前窗口的哈希值和子串的哈希值是否匹配
            if (sstrHash == mstrHash && checkEqual(mstr, i, i + m - 1, sstr, 0, m - 1)) {
                result.add(i);
            }

            // 计算下一个窗口的哈希值
            if (i < n - m) {
                mstrHash = reCalculateHash(mstr, i, i + m, mstrHash, m);
            }
        }

        return result;
    }

    // 计算字符串的初始哈希值
    private long calculateHash(String str, int end) {
        long hash = 0;
        for (int i = 0; i < end; i++) {
            hash += (long) (str.charAt(i) * Math.pow(PRIME, i));
        }
        return hash;
    }

    // 重新计算哈希值
    private long reCalculateHash(String str, int oldIndex, int newIndex, long oldHash, int patternLen) {
        long newHash = oldHash - str.charAt(oldIndex);
        newHash = newHash / PRIME;
        newHash += (long) (str.charAt(newIndex) * Math.pow(PRIME, patternLen - 1));
        return newHash;
    }

    // 逐个对比，检查字符串是否相等
    private boolean checkEqual(String str1, int start1, int end1, String str2, int start2, int end2) {
        while (start1 <= end1 && start2 <= end2) {
            if (str1.charAt(start1) != str2.charAt(start2)) {
                return false;
            }
            start1++;
            start2++;
        }
        return true;
    }
}
